package segmentTree;

//绘图用的类，非线段树，此部分不需要掌握
class TreeNode {
	public String value;
	public TreeNode left, right;
	public TreeNode(String name, TreeNode left, TreeNode right) {
		this.value = name;
		this.left = left;
		this.right = right;
	}
	public StringBuilder toString(StringBuilder prefix, boolean isTail, StringBuilder sb) {
		if (right != null) {
			right.toString(new StringBuilder().append(prefix).append(isTail ? "│   " : "    "), false, sb);
		}
		sb.append(prefix).append(isTail ? "└── " : "┌── ").append(value.toString()).append("\n");
		if (left != null) {
			left.toString(new StringBuilder().append(prefix).append(isTail ? "    " : "│   "), true, sb);
		}
		return sb;
	}
	@Override
	public String toString() {
		return this.toString(new StringBuilder(), true, new StringBuilder()).toString();
	}
}

//线段树节点
class SegTree{
	public int l; //节点表示区间的左界
	public int r; //节点表示区间的右届
	public int data; //节点数据
	public int lz = -1; //lazy标记，-1表示未设置
	public SegTree(int l, int r) {
		this.l = l;
		this.r = r;
	}
	public String toString() {
		return String.format("%d[lz:%d]", this.data,this.lz);
	}
}

public class Main {
	//数据长度
	public static int N=10;
	
	//线段树原数组，下标从1开始计算
	public static int[] a = {0,1,4,5,8,6,2,3,9,10,7};
	
	//线段树，数组表示，长度必须为原数组4倍
	public static SegTree[] segTree = new SegTree[N*4];
	
	// 返回左儿子编号，参数p为父节点编号
	public static int lc(int p) {
		// 左儿子编号p*2
		return p << 1; //位运算提高效率
	}

	// 返回右儿子编号，参数p为父节点编号
	public static int rc(int p) {
		// 右儿子编号p*2+1
		return p << 1 | 1; //位运算提高效率
	}
	
	//从下往上传递区间值，放入节点
	//此处的p是叶子节点
	private static void pushUp(int k) {
		//维护区间和情况
		//segTree[k].data = segTree[lc(k)].data + segTree[rc(k)].data;
		
		//维护最小值情况
		//segTree[k].data = Math.min(segTree[lc(k)].data,segTree[rc(k)].data);
		
		//维护最大值情况
		segTree[k].data = Math.max(segTree[lc(k)].data,segTree[rc(k)].data);
		
	}
	
	//构建线段树
	//参数k节点编号
	//参数l，r表示节点k指向的区间[l,r]
	public static void build(int k , int l , int r) {
		//实例化节点
		segTree[k] = new SegTree(l,r);
		//l==r则当前节点为叶子，直接存值
		//叶子节点的l对应原数据的下标
		if(l==r) {
			segTree[k].data = a[l]; 
			return;
		}
		//折半找区间[l,r]的中点
		int mid = (l+r)>>1;
		int lc = lc(k);
		int rc = rc(k);
		//左儿子递归建树
		build(lc,l,mid);
		//右儿子递归建树
		build(rc,mid+1,r);
		//从下往上传递区间值，放入节点
		//此处决定线段树维护区间和或最大值或最小值
		pushUp(k);
	}
	
	//更新线段树节点（单点更新）
	//参数k节点编号
	//参数i表示将a[i]更新为v
	public static void update(int k , int i , int v) {
		//找到了a[i]
		if(segTree[k].l==segTree[k].r&&segTree[k].l==i) {
			segTree[k].data = v; 
			return;
		}
		
		//折半找区间[segTree[k].l,segTree[k].r]的中点
		int mid = (segTree[k].l+segTree[k].r)>>1;
		int lc = lc(k); //左子节点下标
		int rc = rc(k); //右子节点下标
		
		if(i<=mid)
			update(lc,i,v); //左子树更新
		else
			update(rc,i,v); //右子树更新
		
		//从下往上更新区间值，放入节点
		//此处决定线段树维护区间和或最大值或最小值
		pushUp(k);
	}
	
	
	//查询线段树（不带lazy标记的情况）
	//参数k节点编号
	//参数l，r表示求解的（区间和或最大值或最小值）区间[l,r]
	public static int query(int k,int l,int r) {
		//1、查询区间覆盖节点区间，返回节点值（区简解）
		if(segTree[k].l>=l&&segTree[k].r<=r) {
			return segTree[k].data;
		}
		
		//折半找节点区间[segTree[k].l,segTree[k].r]的中点
		int mid = (segTree[k].l+segTree[k].r)>>1;
		//计算节点的左右子节点编号
		int lc = lc(k);
		int rc = rc(k);
		
		//ans变量保存区间[l,r]答案（查询区间最大值）
		int ans=Integer.MIN_VALUE;
		//ans变量保存区间[l,r]答案（查询区间最小值）
		//int ans=Integer.MAX_VALUE;
		//ans变量保存区间[l,r]答案（查询区间和）
		//int ans = 0;
		
		
		//查询区间最大值的情况
		//l与左子树有重叠，则进入左子树递归查询
		if(l<=mid)
			ans = Math.max(ans,query(lc,l,r));
		//r与右子树有重叠，则进入左子树递归查询
		if(r>mid)
			ans = Math.max(ans,query(rc,l,r));
		
		//查询区间最小值的情况
		//l与左子树有重叠，则进入左子树递归查询
//		if(l<=mid)
//			ans = Math.min(ans,query(lc,l,r));
//		//r与右子树有重叠，则进入左子树递归查询
//		if(r>mid)
//			ans = Math.min(ans,query(rc,l,r));
		

		//查询区间和的情况
		//l与左子树有重叠，则进入左子树递归查询
//		if(l<=mid)
//			ans += query(lc,l,r);
//		//r与右子树有重叠，则进入左子树递归查询
//		if(r>mid)
//			ans += query(rc,l,r);
		
		return ans;
	}
	
	//区间更新、查询与懒操作部分代码
	//设置lazy标记
	//参数k节点编号
	//参数v，每个子节点修改后的值
	public static void lazy(int k,int v) {
		
		// 维护区间和的情况，节点值应设置为懒标记值（区间每个点修改后的值）乘区间长度（r-l+1）
		//segTree[k].data = v * (segTree[k].r - segTree[k].l + 1);
				
		//维护区间最大值和最小值的情况
		segTree[k].data = v;
		segTree[k].lz = v;
		
	}
	
	//向下传递懒标记
	//参数k节点编号
	public static void pushDown(int k) {
		
		lazy(lc(k),segTree[k].lz); //下传左子节点
		lazy(rc(k),segTree[k].lz); //下传右子节点
		//清除自身lazy标记（还原为-1）
		segTree[k].lz = -1;
	}
	
	//区间更新（lazy标记）
	//参数k节点编号
	//参数l，r表示将[l,r]区间更新为v
	public static void update(int k , int l , int r , int v) {
		//找到了[l,r]子区间节点
		if(segTree[k].l>=l&&segTree[k].r<=r) {
			//更新节点值并设置lazy
			lazy(k,v);
			return;
		}
		
		//[l,r]和节点表示区间有交集的情况
		//让节点的左右子树去处理
		if(segTree[k].lz!=-1) {
			//如果当前节点有lazy标记则下传给子树
			pushDown(k);
		}
		
		//折半找区间[segTree[k].l,segTree[k].r]的中点
		int mid = (segTree[k].l+segTree[k].r)>>1;
		int lc = lc(k); //左子节点下标
		int rc = rc(k); //右子节点下标
				
		if(l<=mid)
			update(lc,l,r,v); //左子树更新
		
		if(r>mid)
			update(rc,l,r,v); //右子树更新
				
		//从下往上更新区间值，放入节点
		//此处决定线段树维护区间和或最大值或最小值
		pushUp(k);
	}
	
	//查询线段树（带lazy标记的情况）
	//参数k节点编号
	//参数l，r表示求解的（区间和或最大值或最小值）区间[l,r]
	public static int queryl(int k,int l,int r) {
		//1、查询区间覆盖节点区间，返回节点值（区简解）
		if(segTree[k].l>=l&&segTree[k].r<=r) {
			return segTree[k].data;
		}
		
		//[l,r]和节点表示区间有交集的情况
		//让节点的左右子树去处理
		if(segTree[k].lz!=-1) {
			//如果当前节点有lazy标记则下传给子树
			pushDown(k);
		}
		
			
		//折半找节点区间[segTree[k].l,segTree[k].r]的中点
		int mid = (segTree[k].l+segTree[k].r)>>1;
		//计算节点的左右子节点编号
		int lc = lc(k);
		int rc = rc(k);
			
		//ans变量保存区间[l,r]答案（查询区间最大值）
		int ans=Integer.MIN_VALUE;
		//ans变量保存区间[l,r]答案（查询区间最小值）
		//int ans=Integer.MAX_VALUE;
		//ans变量保存区间[l,r]答案（查询区间和）
		//int ans = 0;
			
			
		//查询区间最大值的情况
		//l与左子树有重叠，则进入左子树递归查询
		if(l<=mid)
			ans = Math.max(ans,queryl(lc,l,r));
		//r与右子树有重叠，则进入左子树递归查询
		if(r>mid)
			ans = Math.max(ans,queryl(rc,l,r));
			
		//查询区间最小值的情况
		//l与左子树有重叠，则进入左子树递归查询
//		if(l<=mid)
//			ans = Math.min(ans,queryl(lc,l,r));
//		//r与右子树有重叠，则进入左子树递归查询
//		if(r>mid)
//			ans = Math.min(ans,queryl(rc,l,r));
			

		//查询区间和的情况
		//l与左子树有重叠，则进入左子树递归查询
//		if(l<=mid)
//			ans += queryl(lc,l,r);
//		//r与右子树有重叠，则进入左子树递归查询
//		if(r>mid)
//			ans += queryl(rc,l,r);
			
		return ans;
	}
	

	//绘图代码，非线段树，此部分不需要掌握
	//参数k节点编号
	//参数l，r表示节点k指向的区间[l,r]
	public static TreeNode getTree(int k , int l , int r){
		TreeNode n = null;
		//l==r则当前节点为叶子，直接返回子节点
		if(l==r) {
			n = new TreeNode(String.valueOf(segTree[k].data), null, null);
			return n;
		}
		
		//折半找区间[l,r]的中点
		int mid = (l+r)>>1;
		//获取左子树
		TreeNode lt = getTree(lc(k),l,mid);
		//获取右子树
		TreeNode rt = getTree(rc(k),mid+1,r);
		//返回结果
		n = new TreeNode(String.valueOf(segTree[k]), lt, rt);
		return n;
		
	}

	public static void main(String[] args) {

		//构建线段树
		build(1,1,10);
		//控制台绘图输出，此部分不需要掌握
		TreeNode t = getTree(1,1,10);
		System.out.print(t.toString());
		
		//更新线段树
		System.out.println("更新节点1的值为11:");
		update(1,1,11);
		//控制台绘图输出，此部分不需要掌握
		t = getTree(1,1,10);
		System.out.print(t.toString());
		
		
		System.out.println("查询区间[1,10]:");
		System.out.println(query(1,1,10));
		
		
		System.out.println("查询区间[1,9]:");
		System.out.println(query(1,1,9));
		
		
		System.out.println("查询区间[1,8]:");
		System.out.println(query(1,1,8));
		
		
		System.out.println("查询区间[9,10]:");
		System.out.println(query(1,9,10));
		
		
		System.out.println("查询区间[3,7]:");
		System.out.println(query(1,3,7));
		
		
		System.out.println("查询区间[6,7]:");
		System.out.println(query(1,6,7));
		
		//int[] a = {0,11,4,5,8,6,2,3,9,10,7};
		//修改区间[3,7]的值为12
		System.out.println("修改区间[3,7]的值为12:");
		update(1,3,7,12);
		//int[] a = {0,11,4,12,12,12,12,12,9,10,7};
		//控制台绘图输出，此部分不需要掌握
		t = getTree(1,1,10);
		System.out.print(t.toString());
		
		System.out.println("查询区间[7,10]:");
		System.out.println(queryl(1,7,10));
		
		System.out.println("查询同时更新了线段树节点和lazy标记:");
		//控制台绘图输出，此部分不需要掌握
		t = getTree(1,1,10);
		System.out.print(t.toString());
		
		System.out.println("查询区间[5,10]:");
		System.out.println(queryl(1,5,10));
		
		System.out.println("查询同时更新了线段树节点和lazy标记:");
		//控制台绘图输出，此部分不需要掌握
		t = getTree(1,1,10);
		System.out.print(t.toString());
	}

}
